#include<iostream>
#include<map>
#include<set>
#include <queue>
#include <c++/vector>
#include <c++/unordered_map>
#include <c++/bits/unordered_map.h>

using namespace std;


/**
 *
 * 方法1：平衡树 set
 * 方法2：懒删除最小堆 priority_queue
 *
 *
 * 方法2:
 * index到number的映射（修改index对应的number）       一对一
 * number到index的映射（找到number对应的最小下标）     一对多
 *
 * 堆在C++中就是一个优先队列，C++的优先队列默认是最大堆
 *
 */
class NumberContainers1{
    unordered_map<int ,int> i2n;
    unordered_map<int ,priority_queue<int,vector<int>,greater<>>> n2i;
public:
    NumberContainers1(){

    }

    void change(int index,int number){
        //先不删，后面find的时候，再删
        i2n[index]=number;
        n2i[number].push(index);
    }

    int find(int number){
        //检查堆顶下标对应的元素是否为number，如果不是，说明这个index对应的number已经change过了，直接弹出堆顶
        auto it =n2i.find(number);
        if(it==n2i.end()) return -1;
        auto &q=it->second;
        while (!q.empty() && i2n[q.top()]!=number){//对应的数字不正确，下标就作废了
            q.pop();
        }
        return q.empty() ? -1 : q.top();
    }
};